class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    	string record;
		vector<string> result;
		stack<char> stk;

		Generate(0, n, stk, record, result);
		return result;
    }

	void Generate(int depth, int n, stack<char>& stk, string& record, vector<string>& result) {
		if (depth == 2 * n) {
			if (stk.size() == 0) {
				result.push_back(record);
			}
			return;
		}
		if (stk.size() > 2 * n - depth) {
			return;
		}

		stk.push('(');
		record += '(';
		Generate(depth + 1, n, stk, record, result);
		record.erase(record.length() - 1, 1);
		stk.pop();

		if (stk.size() == 0) {
			return;
		}
		stk.pop();
		record += ')';
		Generate(depth + 1, n, stk, record, result);
		record.erase(record.length() - 1, 1);
		stk.push('(');
	}
};
